package com.ryujung.dp.leetcode_96;
/*
 * @lc app=leetcode.cn id=96 lang=java
 *
 * [96] 不同的二叉搜索树
 */

// @lc code=start
class Solution {

    /**
     * i为根，长度为n的序列，树量为：f(i,n) =G(i-1)*G(n-i)
     * 边界：i>=1,i<=n
     * G(n) = ∑f(i,n) (i取0~n)
     * G(n) = ∑G(i-1)*G(n-i) (i取0~n)
     */
    public static int numTrees(int n) {
        long[] sub = new long[n + 1];
        // 空树情况唯一
        sub[0] = 1L;
        sub[1] = 1L;

        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                sub[i] += sub[j - 1] * sub[i - j];
            }
        }

        return (int) sub[n];
    }

    public static void main(String[] args) {
        System.out.println(numTrees(3));
    }

}
// @lc code=end
